//给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。 
//
// 请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。 
//
// 每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。 
//
// 题目保证一定有解。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,5,9], threshold = 6
//输出：5
//解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
//如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,3,5,7,11], threshold = 11
//输出：3
// 
//
// 示例 3： 
//
// 
//输入：nums = [19], threshold = 5
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 10^4 
// 1 <= nums[i] <= 10^6 
// nums.length <= threshold <= 10^6 
// 
//
// Related Topics 数组 二分查找 👍 143 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        // 排序
        Arrays.sort(nums);
        int n = nums.length;
        int right = nums[n - 1];//right绝对正确，最大值绝对正确
        int left = 0;//left为false
        
        while(left +1 < right){
            int mid = left + (right - left) / 2;
            if(check(mid,nums,threshold)){
                //如果满足要求
                right = mid;//因为要求最小的，所以right是绝对正确而check找的也是正确的。
            }else{
                left = mid;
            }
        }
        return right;
    
    }
    
    public boolean check(int mid ,int[] nums,int threshold) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] + mid - 1) / mid;
            // 如果比threshold大，不用继续直接退出
            if(sum > threshold){
                return false;
            }
        }
        // 如果没有大于threshold那么就是小于的
        return true;
    
    }
}
//leetcode submit region end(Prohibit modification and deletion)
